import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static java.lang.System.err;
import static java.lang.System.out;

/**
 * A Board is represented by 3 ints for black and white pieces and kings, 1 bit
 * for each square. Bits are counted from 0 to 31 with bit 0 in the top left
 * corner, bit 3 in the top right, and bit 31 in the bottom right.
 *
 * Rows are numbered from 0 to 7, top to bottom. Columns are numbered from 0 to
 * 3, left to right.
 */
public final class Board {
    public static final int INIT_BLACK = 0x00000FFF;
    public static final int INIT_WHITE = 0xFFF00000;
    public static final int INIT_KINGS = 0;
    public static final int TOP_ROW = 0xF;
    public static final int BOTTOM_ROW = 0xF0000000;
    public static final int MAX_KINGS = 18;

    private static boolean printParsingErrors = true;

    public int black;
    public int white;
    public int kings;
    public boolean blackToMove;

    public Board() {
        this(INIT_BLACK, INIT_WHITE, INIT_KINGS, true);
    }

    public Board(int black, int white, int kings, boolean blackToMove) {
        this.black = black;
        this.white = white;
        this.kings = kings;
        this.blackToMove = blackToMove;
    }

    public Board(Board original) {
        this.black = original.black;
        this.white = original.white;
        this.kings = original.kings;
        this.blackToMove = original.blackToMove;
    }

    public static Board parseCwb(String... lines) {
        if (lines.length != 9) {
            if (printParsingErrors) {
                err.println("Unexpected number of lines in board. Expected 9"
                            + " lines, got " + lines.length);
            }
            return null;
        }

        int parsedBlack = 0;
        int parsedWhite = 0;
        int parsedKings = 0;
        boolean parsedBlackToMove;

        int bitNbr = 0;
        for (int i = 0; i < 8; i++) {
            String line = lines[i].trim();
            String[] tokens = line.split("\\s+");
            if (tokens.length != 4) {
                if (printParsingErrors) {
                    err.println("Unexpected number of tokens. Expected 4 tokens"
                                + ", got " + tokens.length + ": "
                                + Arrays.toString(tokens));
                }
                return null;
            }

            for (int j = 0; j < 4; j++) {
                String token = tokens[j];
                if (token.length() != 1) {
                    if (printParsingErrors) {
                        err.println("Unexpected token length. Expected length"
                                    + " of 1, got length" + token.length()
                                    + ": '" + token + "'.");
                    }
                    return null;
                }

                int bit = 1 << bitNbr;
                char c = token.charAt(0);
                switch (c) {
                case 'B':
                    parsedBlack |= bit;
                    parsedKings |= bit;
                    break;
                case 'b':
                    parsedBlack |= bit;
                    break;
                case 'W':
                    parsedWhite |= bit;
                    parsedKings |= bit;
                    break;
                case 'w':
                    parsedWhite |= bit;
                    break;
                case '-':
                    // Do nothing
                    break;
                default:
                    if (printParsingErrors) {
                        err.printf("Unexpected character %c. Expected one of"
                                   + " -, b, B, w, or W\n", c);
                    }
                    return null;
                }
                bitNbr++;
            }
        }

        char t = lines[8].trim().charAt(0);
        switch (t) {
        case 'B':
        case 'b':
            parsedBlackToMove = true;
            break;
        case 'W':
        case 'w':
            parsedBlackToMove = false;
            break;
        default:
            if (printParsingErrors) {
                err.printf("Unexpected character %c. Expected one of"
                           + " b, B, w, or W\n", t);
            }
            return null;
        }

        return new Board(parsedBlack, parsedWhite, parsedKings,
                         parsedBlackToMove);
    }

    public static Board parseWdp(String string) {
        if (string.length() != 41) {
            if (printParsingErrors) {
                err.println("Unexpected length of string. Expected a length of"
                            + " 41, got " + string.length());
            }
            return null;
        }

        int parsedBlack = 0;
        int parsedWhite = 0;
        int parsedKings = 0;
        boolean parsedBlackToMove;

        int i = 0;
        int bitNbr = 0;
        while (i < 40) {
            for (int j = 0; j < 4; j++) {
                int bit = 1 << bitNbr;
                char c = string.charAt(i);
                switch (c) {
                case 'B':
                    parsedBlack |= bit;
                    parsedKings |= bit;
                    break;
                case 'b':
                    parsedBlack |= bit;
                    break;
                case 'W':
                    parsedWhite |= bit;
                    parsedKings |= bit;
                    break;
                case 'w':
                    parsedWhite |= bit;
                    break;
                case '.':
                    // Do nothing
                    break;
                default:
                    if (printParsingErrors) {
                        err.printf("Unexpected character '%c'. Expected one of"
                                   + " ., b, B, w, or W\n", c);
                    }
                    return null;
                }
                i++;
                bitNbr++;
            }

            char s = string.charAt(i);
            if (s != ' ') {
                if (printParsingErrors) {
                    err.printf("Unexpected character '%c'. Expected ' '\n", s);
                }
                return null;
            }
            i++;
        }

        char t = string.charAt(40);
        switch (t) {
        case 'B':
        case 'b':
            parsedBlackToMove = true;
            break;
        case 'W':
        case 'w':
            parsedBlackToMove = false;
            break;
        default:
            if (printParsingErrors) {
                err.printf("Unexpected character '%c'. Expected one of"
                           + " b, B, w, or W\n", t);
            }
            return null;
        }

        return new Board(parsedBlack, parsedWhite, parsedKings,
                         parsedBlackToMove);
    }


    public static void setPrintParsingErrors(boolean printEm) {
        printParsingErrors = printEm;
    }


    @Override
    public boolean equals(Object obj)
    {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (this.getClass() != obj.getClass())
            return false;

        Board rhs = (Board) obj;

        return black == rhs.black && white == rhs.white && kings == rhs.kings
            && blackToMove == rhs.blackToMove;
    }



    public boolean isSame(Board rhs)
    {
        return black == rhs.black && white == rhs.white && kings == rhs.kings
            && blackToMove == rhs.blackToMove;
    }


    @Override
    public int hashCode() {
        if (blackToMove) {
            return (black | white) + kings;
        } else {
            return ~((black | white) + kings);
        }
    }


    public void makeMove(int[] move) {
        int nbrMoves = move.length - 1;
        for (int i = 0; i < nbrMoves; i++) {
            makeMove(move[i], move[i + 1]);
        }
    }

    /**
     * Make a move on this board. Doesn't check if the requested move is valid
     * or not.
     */
    public void makeMove(int fromPos, int toPos) {
        final int fromIndex = fromPos - 1;
        final int toIndex = toPos - 1;

        // Pick out the piece on the fromPos square
        int blackBit = (black >>> fromIndex) & 1;
        int whiteBit = (white >>> fromIndex) & 1;
        int kingBit  = (kings >>> fromIndex) & 1;

        // Move the piece to the toPos square
        int blackDest = blackBit << toIndex;
        int whiteDest = whiteBit << toIndex;
        int kingDest  = kingBit << toIndex;

        // Crown if not king and either black on last or white on first row
        kingDest |= (blackDest & BOTTOM_ROW) | (whiteDest & TOP_ROW);

        // Move the piece to the toPos square
        black |= blackDest;
        white |= whiteDest;
        kings |= kingDest;

        // Remove the piece from the fromPos square
        int removeMask = ~(1 << fromIndex);
        black &= removeMask;
        white &= removeMask;
        kings &= removeMask;


        // Find squares containing captured pieces
        int distance = toPos - fromPos;
        int rowModifier = (fromIndex >>> 2) & 1; // 0 for even rows, 1 for odd rows
        int capturedSquare = -1;

        switch (distance) {
        case -9:
            // Capturing north west
            capturedSquare = fromPos - 4;
            break;
        case -7:
            // Capturing north east
            capturedSquare = fromPos - 3;
            break;
        case 7:
            // Capturing south west
            capturedSquare = fromPos + 4;
            break;
        case 9:
            // Capturing south east
            capturedSquare = fromPos + 5;
            break;
        }
        capturedSquare -= rowModifier;

        // Remove captured pieces
        if(capturedSquare > -1) {

	    black &= ~(1 << (capturedSquare - 1));
            white &= ~(1 << (capturedSquare - 1));
            kings &= ~(1 << (capturedSquare - 1));

        }


    }




    /**
     * A sanity check for the board. Is the board state valid?
     */
    public boolean isSane() {
        // Black and white pieces can't be on the same square
        if ((black & white) != 0) {
            return false;
        }

        // King markers must be on the same square as a black or white marker
        if ((kings & (~(black | white))) != 0) {
            return false;
        }

        // There can't be more than 12 black or white pieces
        if (BitUtils.countBits(black) > 12) {
            return false;
        }
        if (BitUtils.countBits(white) > 12) {
            return false;
        }

        // There can't be more than 18 kings (that should probably be lowered)
        if (BitUtils.countBits(kings) > MAX_KINGS) {
            return false;
        }

        return true;
    }



    public boolean isLegalMove(int[] move) {
        if (move.length < 2) {
            return false;
        }

        boolean legalMove = true;
        Board boardCopy = new Board(this);
        boolean mustJump = move.length > 2;
        int nbrMoves = move.length - 1;
        int i = 0;
        while (legalMove && i < nbrMoves) {
            legalMove = boardCopy.isLegalMove(move[i], move[i + 1], mustJump);
            if (legalMove) {
                boardCopy.makeMove(move[i], move[i + 1]);
            }
            i++;
        }

        return legalMove;
    }

    /**
     * Does the arguments describe a valid move on this board? The method can't
     * handle more than one jump at the moment.
     *
     *<pre>
     * Making a normal move:
     * Starting on an even row     Starting on an odd row
     * -4 O   O -3                 -5 O   O -4
     *     \ /                         \ /
     *      O                           O
     *     / \                         / \
     * +4 O   O +5                 +3 O   O +4
     *
     * Capturing:
     * Starting on an even row     Starting on an odd row
     * -9 O       O -7             -9 O       O -7
     *     \     /                     \     /
     *   -4 o   o -3                 -5 o   o -4
     *       \ /                         \ /
     *        O                           O
     *       / \                         / \
     *   +4 o   o +5                 +3 o   o +4
     *     /     \                     /     \
     * +7 O       O +9             +7 O       O +9
     *</pre>
     */
    public boolean isLegalMove(int from, int to, boolean mustJump) {
        // Is index out of range?
        if ((from < 1) || (from > 32) || (to < 1) || (to > 32)) {
            return false;
        }

        final int fromIndex = from - 1;
        final int toIndex = to - 1;

        int movingColor = blackToMove ? black : white;
        // There has to be a piece on the from square of the same color as the
        // acting player
        if (((movingColor >>> fromIndex) & 1) == 0) {
            return false;
        }

        // There can't be a piece on the to square
        if ((((black | white) >>> toIndex) & 1) != 0) {
            return false;
        }

        int distance = to - from;
        // rowModifier will be 0 for even rows and 1 for odd rows
        int rowModifier = (fromIndex >>> 2) & 1;
        boolean evenRow = rowModifier == 0;

        boolean isLegalDistance = false;
        boolean movingLeft = true;
        boolean isCapturing = false;
        int capturedSquare = -1;

        switch (distance) {
        case -9:
            // Capturing north west
            isLegalDistance = true;
            isCapturing = true;
            capturedSquare = from - 4;
            break;
        case -7:
            // Capturing north east
            isLegalDistance = true;
            movingLeft = false;
            isCapturing = true;
            capturedSquare = from - 3;
            break;
        case 7:
            // Capturing south west
            isLegalDistance = true;
            isCapturing = true;
            capturedSquare = from + 4;
            break;
        case 9:
            // Capturing south east
            isLegalDistance = true;
            movingLeft = false;
            isCapturing = true;
            capturedSquare = from + 5;
            break;
        }
        capturedSquare -= rowModifier;

        int jumpers = mustJump();

        int modifiedDistance = distance + rowModifier;
        if ((jumpers == 0) && (!isCapturing) && (!mustJump)) {
            switch (modifiedDistance) {
            case -4:
                // Moving north west
                isLegalDistance = true;
                break;
            case -3:
                // Moving north east
                isLegalDistance = true;
                movingLeft = false;
                break;
            case 4:
                // Moving south west
                isLegalDistance = true;
                break;
            case 5:
                // Moving south east
                isLegalDistance = true;
                movingLeft = false;
                break;
            }
        }

        if (!isLegalDistance) {
            return false;
        }

        // A piece can't move from the left edge to the right or vice versa
        int colIndex = fromIndex & 3;
        if ((colIndex == 0) && (!evenRow) && movingLeft) {
            return false;
        }
        if ((colIndex == 0) && evenRow && movingLeft && isCapturing) {
            return false;
        }
        if ((colIndex == 3) && evenRow && (!movingLeft)) {
            return false;
        }
        if ((colIndex == 3) && (!evenRow) && (!movingLeft) && isCapturing) {
            return false;
        }

        boolean isKing = ((kings >>> fromIndex) & 1) == 1;
        // Black men can't move up
        if (blackToMove && (!isKing) && (distance < 0)) {
            return false;
        }

        // White men can't move down
        if ((!blackToMove) && (!isKing) && (distance > 0)) {
            return false;
        }

        if (isCapturing) {
            // A jumping piece should capture a piece of the opposing color
            int capturedColor = blackToMove ? white : black;

            // There has to be a piece of the opposing color on the square we
            // jump over
            if (((capturedColor >>> (capturedSquare - 1)) & 1) == 0) {
                return false;
            }
        }

        return true;
    }




    private static final int EVEN_NW      = 0x0F0F0F00;
    private static final int EVEN_JUMP_NW = 0x0E0E0E00;
    private static final int ODD_NW       = 0xE0E0E0E0;
    private static final int ODD_JUMP_NW  = 0xE0E0E000;

    private static final int EVEN_NE      = 0x07070700;
    private static final int EVEN_JUMP_NE = 0x07070700;
    private static final int ODD_NE       = 0xF0F0F0F0;
    private static final int ODD_JUMP_NE  = 0x70707000;

    private static final int EVEN_SW      = 0x0F0F0F0F;
    private static final int EVEN_JUMP_SW = 0x000E0E0E;
    private static final int ODD_SW       = 0x00E0E0E0;
    private static final int ODD_JUMP_SW  = 0x00E0E0E0;

    private static final int EVEN_SE      = 0x07070707;
    private static final int EVEN_JUMP_SE = 0x00070707;
    private static final int ODD_SE       = 0x00F0F0F0;
    private static final int ODD_JUMP_SE  = 0x00707070;

    public int mustJump() {
        int empty = ~(black | white);

        int movingNorth;
        int movingSouth;
        int otherColor;
        if (blackToMove) {
            movingNorth = black & kings;
            movingSouth = black;
            otherColor = white;
        } else {
            movingNorth = white;
            movingSouth = white & kings;
            otherColor = black;
        }

        int jumpers = 0;
        if (movingNorth != 0) {
            jumpers = northJumpers(movingNorth, otherColor, empty,
                                   EVEN_JUMP_NW, ODD_NW, 9, 4);
            jumpers |= northJumpers(movingNorth, otherColor, empty,
                                    ODD_JUMP_NW, EVEN_NW, 9, 5);
            jumpers |= northJumpers(movingNorth, otherColor, empty,
                                    EVEN_JUMP_NE, ODD_NE, 7, 3);
            jumpers |= northJumpers(movingNorth, otherColor, empty,
                                    ODD_JUMP_NE, EVEN_NE, 7, 4);
        }
        if (movingSouth != 0) {
            jumpers |= southJumpers(movingSouth, otherColor, empty,
                                   EVEN_JUMP_SW, ODD_SW, 7, 4);
            jumpers |= southJumpers(movingSouth, otherColor, empty,
                                   ODD_JUMP_SW, EVEN_SW, 7, 3);
            jumpers |= southJumpers(movingSouth, otherColor, empty,
                                   EVEN_JUMP_SE, ODD_SE, 9, 5);
            jumpers |= southJumpers(movingSouth, otherColor, empty,
                                   ODD_JUMP_SE, EVEN_SE, 9, 4);
        }

        return jumpers;
    }

    public int northJumpers(int movingColor, int otherColor, int empty,
                            int jumpMask, int capturedMask,
                            int moveDistance, int capturedDistance)
    {
        return (movingColor & jumpMask)
            & (empty << moveDistance)
            & ((otherColor & capturedMask) << capturedDistance);
    }

    public int southJumpers(int movingColor, int otherColor, int empty,
                            int jumpMask, int capturedMask,
                            int moveDistance, int capturedDistance)
    {
        return (movingColor & jumpMask)
            & (empty >>> moveDistance)
            & ((otherColor & capturedMask) >>> capturedDistance);
    }

    public boolean northJumps(int movingColor, int movingNorth, int otherColor,
                              int theKings, int empty,
                              int jumpMask, int capturedMask,
                              int moveDistance, int capturedDistance,
                              ArrayList<Board> moves)
    {
        boolean couldJumpAgain = false;

        int jumpers = northJumpers(movingNorth, otherColor, empty, jumpMask,
                                  capturedMask, moveDistance, capturedDistance);

        while (jumpers != 0) {
            // Pick out the least significant jumper
            int jumper = jumpers & (-jumpers);
            // Remove it
            jumpers ^= jumper;

            // Remove it from the moving color
            int newMovingColor = movingColor ^ jumper;
            int jumperNewPos = jumper >>> moveDistance;
            // Place the jumper at its new position
            newMovingColor |= jumperNewPos;

            // Get the king bit for the jumper
            int jumperKing = theKings & jumper;
            // Remove the king bit from its old position (if there was a king)
            int newKings = theKings & (~jumperKing);
            // Place the king bit at the jumper's new position
            int kingNewPos = jumperKing >>> moveDistance;
            newKings |= kingNewPos;

            // Remove the captured piece
            int capturedPos = jumper >>> capturedDistance;
            int newOtherColor = otherColor ^ capturedPos;

            // Remove a captured king (if there was one)
            newKings &= ~capturedPos;

            // Add the from square and captured square to empty
            // and remove the destination square
            int newEmpty = (empty & (~jumperNewPos)) | jumper | capturedPos;

            // If the jumper reaches the end of the board, make it king
            int becomeKing = (jumperNewPos ^ kingNewPos) & TOP_ROW;
            newKings |= becomeKing;

            // Newly crowned kings can't jump further
            if (becomeKing == 0) {
                int newMovingNorth;
                int newMovingSouth;
                if (blackToMove) {
                    newMovingNorth = kingNewPos;
                    newMovingSouth = jumperNewPos;
                } else {
                    newMovingNorth = jumperNewPos;
                    newMovingSouth = kingNewPos;
                }

                // Try to jump further in all possible directions with just this
                // jumper
                if (newMovingNorth != 0) {
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_NW, ODD_NW, 9, 4, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_NW, EVEN_NW, 9, 5, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_NE, ODD_NE, 7, 3, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_NE, EVEN_NE, 7, 4, moves);
                }
                if (newMovingSouth != 0) {
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_SW, ODD_SW, 7, 4, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_SW, EVEN_SW, 7, 3, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_SE, ODD_SE, 9, 5, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_SE, EVEN_SE, 9, 4, moves);
                }
            }

            // If this jumper couldn't jump further, add this jump as a move
            if (!couldJumpAgain) {
                boolean newBlackToMove = ! blackToMove;
                if (blackToMove) {
                    moves.add(new Board(newMovingColor, newOtherColor, newKings,
                                        newBlackToMove));
                } else {
                    moves.add(new Board(newOtherColor, newMovingColor, newKings,
                                        newBlackToMove));
                }

                couldJumpAgain = true;
            }
        }

        return couldJumpAgain;
    }

    public boolean southJumps(int movingColor, int movingSouth, int otherColor,
                              int theKings, int empty,
                              int jumpMask, int capturedMask,
                              int moveDistance, int capturedDistance,
                              ArrayList<Board> moves)
    {
        boolean couldJumpAgain = false;

        int jumpers = southJumpers(movingSouth, otherColor, empty, jumpMask,
                                  capturedMask, moveDistance, capturedDistance);

        while (jumpers != 0) {
            // Pick out the least significant jumper
            int jumper = jumpers & (-jumpers);
            // Remove it
            jumpers ^= jumper;

            // Remove it from the moving color
            int newMovingColor = movingColor ^ jumper;
            int jumperNewPos = jumper << moveDistance;
            // Place the jumper at its new position
            newMovingColor |= jumperNewPos;

            // Get the king bit for the jumper
            int jumperKing = theKings & jumper;
            // Remove the king bit from its old position (if there was a king)
            int newKings = theKings & (~jumperKing);
            // Place the king bit at the jumper's new position
            int kingNewPos = jumperKing << moveDistance;
            newKings |= kingNewPos;

            // Remove the captured piece
            int capturedPos = jumper << capturedDistance;
            int newOtherColor = otherColor ^ capturedPos;

            // Remove a captured king (if there was one)
            newKings &= ~capturedPos;

            // Add the from square and captured square to empty
            // and remove the destination square
            int newEmpty = (empty & (~jumperNewPos)) | jumper | capturedPos;

            // If the jumper reaches the end of the board, make it king
            int becomeKing = (jumperNewPos ^ kingNewPos) & BOTTOM_ROW;
            newKings |= becomeKing;

            // Newly crowned kings can't jump further
            if (becomeKing == 0) {
                int newMovingNorth;
                int newMovingSouth;
                if (blackToMove) {
                    newMovingNorth = kingNewPos;
                    newMovingSouth = jumperNewPos;
                } else {
                    newMovingNorth = jumperNewPos;
                    newMovingSouth = kingNewPos;
                }

                // Try to jump further in all possible directions with just this
                // jumper
                if (newMovingNorth != 0) {
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_NW, ODD_NW, 9, 4, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_NW, EVEN_NW, 9, 5, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_NE, ODD_NE, 7, 3, moves);
                    couldJumpAgain |= northJumps(newMovingColor, newMovingNorth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_NE, EVEN_NE, 7, 4, moves);
                }
                if (newMovingSouth != 0) {
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_SW, ODD_SW, 7, 4, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_SW, EVEN_SW, 7, 3, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          EVEN_JUMP_SE, ODD_SE, 9, 5, moves);
                    couldJumpAgain |= southJumps(newMovingColor, newMovingSouth,
                                          newOtherColor, newKings, newEmpty,
                                          ODD_JUMP_SE, EVEN_SE, 9, 4, moves);
                }
            }

            // If this jumper couldn't jump further, add this jump as a move
            if (!couldJumpAgain) {
                boolean newBlackToMove = ! blackToMove;
                if (blackToMove) {
                    moves.add(new Board(newMovingColor, newOtherColor, newKings,
                                        newBlackToMove));
                } else {
                    moves.add(new Board(newOtherColor, newMovingColor, newKings,
                                        newBlackToMove));
                }

                couldJumpAgain = true;
            }
        }

        return couldJumpAgain;
    }

    public int northMovers(int movingColor, int otherColor, int empty,
                           int moveMask, int moveDistance)
    {
        return (movingColor & moveMask) & (empty << moveDistance);
    }

    public int southMovers(int movingColor, int otherColor, int empty,
                           int moveMask, int moveDistance)
    {
        return (movingColor & moveMask) & (empty >>> moveDistance);
    }

    public void northMoves(int movingColor, int movingNorth, int otherColor,
                           int empty, int moveMask, int moveDistance,
                           ArrayList<Board> moves)
    {
        int movers = northMovers(movingNorth, otherColor, empty, moveMask,
                                 moveDistance);

        while (movers != 0) {
            // Pick out the least significant mover
            int mover = movers & (-movers);
            // Remove it
            movers ^= mover;

            // Remove it from the moving color
            int newMovingColor = movingColor ^ mover;
            int moverNewPos = mover >>> moveDistance;
            // Place the mover at its new position
            newMovingColor |= moverNewPos;

            // Get the king bit for the mover
            int moverKing = kings & mover;
            // Remove the king bit from its old position (if there was a king)
            int newKings = kings & (~moverKing);
            // Place the king bit at the mover's new position
            newKings |= moverKing >>> moveDistance;

            boolean newBlackToMove = ! blackToMove;
            if (blackToMove) {
                moves.add(new Board(newMovingColor, otherColor, newKings,
                                    newBlackToMove));
            } else {
                // If the mover reaches the end of the board, make it king
                int becomeKing = moverNewPos & TOP_ROW;
                newKings |= becomeKing;
                moves.add(new Board(otherColor, newMovingColor, newKings,
                                    newBlackToMove));
            }
        }
    }

    public void southMoves(int movingColor, int movingSouth, int otherColor,
                           int empty, int moveMask, int moveDistance,
                           ArrayList<Board> moves)
    {
        int movers = southMovers(movingSouth, otherColor, empty, moveMask,
                                 moveDistance);

        while (movers != 0) {
            // Pick out the least significant mover
            int mover = movers & (-movers);
            // Remove it
            movers ^= mover;

            // Remove it from the moving color
            int newMovingColor = movingColor ^ mover;
            int moverNewPos = mover << moveDistance;
            // Place the mover at its new position
            newMovingColor |= moverNewPos;

            // Get the king bit for the mover
            int moverKing = kings & mover;
            // Remove the king bit from its old position (if there was a king)
            int newKings = kings & (~moverKing);
            // Place the king bit at the mover's new position
            newKings |= moverKing << moveDistance;

            boolean newBlackToMove = ! blackToMove;
            if (blackToMove) {
                // If the mover reaches the end of the board, make it king
                int becomeKing = moverNewPos & BOTTOM_ROW;
                newKings |= becomeKing;
                moves.add(new Board(newMovingColor, otherColor, newKings,
                                    newBlackToMove));
            } else {
                moves.add(new Board(otherColor, newMovingColor, newKings,
                                    newBlackToMove));
            }
        }
    }

    public ArrayList<Board> generateMoves() {
        ArrayList<Board> moves = new ArrayList<Board>();
        generateJumps(moves);
        if (moves.size() == 0) {
            generateSteps(moves);
        }

        return moves;
    }

    public void generateJumps(ArrayList<Board> moves) {
        int empty = ~(black | white);

        int movingColor;
        int movingNorth;
        int movingSouth;
        int otherColor;
        if (blackToMove) {
            movingColor = black;
            movingNorth = black & kings;
            movingSouth = black;
            otherColor = white;
        } else {
            movingColor = white;
            movingNorth = white;
            movingSouth = white & kings;
            otherColor = black;
        }

        if (movingNorth != 0) {
            northJumps(movingColor, movingNorth, otherColor, kings, empty,
                       EVEN_JUMP_NW, ODD_NW, 9, 4, moves);
            northJumps(movingColor, movingNorth, otherColor, kings, empty,
                       ODD_JUMP_NW, EVEN_NW, 9, 5, moves);
            northJumps(movingColor, movingNorth, otherColor, kings, empty,
                       EVEN_JUMP_NE, ODD_NE, 7, 3, moves);
            northJumps(movingColor, movingNorth, otherColor, kings, empty,
                       ODD_JUMP_NE, EVEN_NE, 7, 4, moves);
        }
        if (movingSouth != 0) {
            southJumps(movingColor, movingSouth, otherColor, kings, empty,
                       EVEN_JUMP_SW, ODD_SW, 7, 4, moves);
            southJumps(movingColor, movingSouth, otherColor, kings, empty,
                       ODD_JUMP_SW, EVEN_SW, 7, 3, moves);
            southJumps(movingColor, movingSouth, otherColor, kings, empty,
                       EVEN_JUMP_SE, ODD_SE, 9, 5, moves);
            southJumps(movingColor, movingSouth, otherColor, kings, empty,
                       ODD_JUMP_SE, EVEN_SE, 9, 4, moves);
        }
    }

    public void generateSteps(ArrayList<Board> moves) {
        int empty = ~(black | white);

        int movingColor;
        int movingNorth;
        int movingSouth;
        int otherColor;
        if (blackToMove) {
            movingColor = black;
            movingNorth = black & kings;
            movingSouth = black;
            otherColor = white;
        } else {
            movingColor = white;
            movingNorth = white;
            movingSouth = white & kings;
            otherColor = black;
        }

        if (movingNorth != 0) {
            northMoves(movingColor, movingNorth, otherColor, empty, EVEN_NW,
                       4, moves);
            northMoves(movingColor, movingNorth, otherColor, empty, ODD_NW,
                       5, moves);
            northMoves(movingColor, movingNorth, otherColor, empty, EVEN_NE,
                       3, moves);
            northMoves(movingColor, movingNorth, otherColor, empty, ODD_NE,
                       4, moves);
        }
        if (movingSouth != 0) {
            southMoves(movingColor, movingSouth, otherColor, empty, EVEN_SW,
                       4, moves);
            southMoves(movingColor, movingSouth, otherColor, empty, ODD_SW,
                       3, moves);
            southMoves(movingColor, movingSouth, otherColor, empty, EVEN_SE,
                       5, moves);
            southMoves(movingColor, movingSouth, otherColor, empty, ODD_SE,
                       4, moves);
        }
    }

    public static Board mirrorBoard(Board board) {
        int mirrorBlack = 0;
        int mirrorWhite = 0;
        int mirrorKings = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            mirrorBlack |= ((board.white >>> i) & 1) << (31 - i);
            mirrorWhite |= ((board.black >>> i) & 1) << (31 - i);
            mirrorKings |= ((board.kings >>> i) & 1) << (31 - i);
        }

        return new Board(mirrorBlack, mirrorWhite, mirrorKings,
                         !board.blackToMove);
    }
}
